home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 06 - 1990 / 06.09 Sep 90 / Canon Sources / Fast Canon / Canon.c next >
Encoding:
C/C++ Source or Header  |  1990-02-07  |  24.8 KB  |  1,213 lines  |  [TEXT/nX^n]
  1. //////////////////////////////////////////////////////////////////
  2. //    
  3. //        Canon.c
  4. //        -------
  5. //        New MPW Canon tool
  6. //    
  7. //////////////////////////////////////////////////////////////////
  8.     
  9. #pragma load "managers"
  10.     
  11. //////////////////////////////////////////////////////////////////
  12. //    
  13. //        Constants and Macros
  14. //    
  15. //////////////////////////////////////////////////////////////////
  16.     
  17. #define nil                    0
  18.     
  19. #define stdinfd            0
  20. #define stdoutfd            1
  21. #define stderrfd            2
  22.     
  23. #define stdunit(x)        ((x >= stdinfd) && (x <= stderrfd))
  24. #define notstdunit(x)    (x > stderrfd)
  25.  
  26. #define nombuffsize        1024
  27. #define truebuffsize        1200
  28.  
  29. #define classcount        15
  30. #define idstate            7
  31.  
  32. #define blocksize            200
  33.     
  34. //////////////////////////////////////////////////////////////////
  35. //    
  36. //        Types
  37. //    
  38. //////////////////////////////////////////////////////////////////
  39.     
  40. typedef enum {false, true} logical;
  41. typedef enum {nocode, pascalcode, ccode} codetype;
  42.  
  43. typedef struct node
  44.     {
  45.     char                *key;
  46.     struct node        *left;
  47.     struct node        *right;
  48.     int                balance;
  49.     char                *data;
  50.     } node;
  51.  
  52. typedef struct block
  53.     {
  54.     struct block    *previous;
  55.     int                free;
  56.     node                data[blocksize];
  57.     } block;
  58.     
  59. //////////////////////////////////////////////////////////////////
  60. //    
  61. //        Globals
  62. //    
  63. //////////////////////////////////////////////////////////////////
  64.     
  65.     unsigned char    *CASETABLE;
  66.     block                *MEMORY = nil;
  67.     Handle            DICTIONARY;
  68.     char                NOTHING[] = "";
  69.     
  70. //////////////////////////////////////////////////////////////////
  71. //    
  72. //        Prototypes
  73. //    
  74. //////////////////////////////////////////////////////////////////
  75.     
  76.     void initmac();
  77.     int openoutput(char *thename, int output);
  78.     int readinput(int input, Handle inbuffer);
  79.     int filter(char *inbuffer, int buffersize, int output,
  80.                     codetype language, node *symbols);
  81.     int writeoutput(int output, char *outbuffer, int buffersize);
  82.     node *parser(char *dictname, codetype language);
  83.     char *gettoken(char *buffer, int buffersize,
  84.                     char *classtable, char *statetable, int *thetoken);
  85.     node *createnode(char *thekey, char *thedata);
  86.     unsigned int insert(node *parent, char *thekey, char *thedata, int depth);
  87.     node *lookup(node *thetable, char *thekey);
  88.     void destroy();
  89.     void dump(node *thenode);
  90.     int compare(unsigned char *string1, unsigned char *string2);
  91.     
  92. //////////////////////////////////////////////////////////////////
  93. //
  94. //        main
  95. //        ----
  96. //        the "main" routine reads and interprets the command line,
  97. //        reads the dictionary file, and filters the input
  98. //
  99. //////////////////////////////////////////////////////////////////
  100.     
  101. int main(int argc, char *argv[])
  102.     {
  103.     
  104.     int                output;
  105.     logical            sensitive;
  106.     codetype            language;
  107.     char                *outputname;
  108.     char                *dictname;
  109.     logical            errors;
  110.     int                index;
  111.     char                *thetail;
  112.     Handle            thehandle;
  113.     node                *symbols;
  114.     int                input;
  115.     int                buffersize;
  116.     
  117.     initmac();
  118.     
  119. //    "output" is the fd of the output file, initially stdout
  120. //    "sensitive" is the case sensitivity, initially insensitive
  121. //    "language" is the language to parse, initially unknown
  122.     
  123.     output = stdoutfd;
  124.     sensitive = false;
  125.     language = nocode;
  126.     
  127. //    "outputname" is the name of the output file
  128. //    "dictname" is the name of the dictionary file
  129. //    "errors" is the error flag, initially indicating no errors
  130.     
  131.     outputname = nil;
  132.     dictname = nil;
  133.     errors = false;
  134.     
  135. //    command line interpreter: first pass
  136.     
  137.     for (index = 1; index < argc; index++)
  138.         {
  139.         
  140.         if (argv[index][0] == '-')
  141.             {
  142.             
  143.             switch (argv[index][1])
  144.                 {
  145.     
  146. //    "-p" and "-c" options set language type;
  147. //        these override any previous setting
  148.                 
  149.                 case 'C':
  150.                 case 'c':
  151.                     language = ccode;
  152.                     break;
  153.                 
  154.                 case 'P':
  155.                 case 'p':
  156.                     language = pascalcode;
  157.                     break;
  158.     
  159. //    "-s" option make Canon case sensitive
  160.                 
  161.                 case 'S':
  162.                 case 's':
  163.                     sensitive = true;
  164.                     break;
  165.     
  166. //    "-o" option names the output file; remember the name
  167. //        and read the file later
  168.                 
  169.                 case 'O':
  170.                 case 'o':
  171.                     index++;
  172.                     if (outputname == nil)
  173.                         outputname = argv[index];
  174.                     else
  175.                         {
  176.                         fprintf(stderr, "Error - multiple output "
  177.                                         "files %s and %s!\n",
  178.                                         outputname, argv[index]);
  179.                         errors = true;
  180.                         }
  181.                     break;
  182.     
  183. //    "-d" option names the dictionary file; remember the name
  184. //        and read the file later
  185.                 
  186.                 case 'D':
  187.                 case 'd':
  188.                     index++;
  189.                     if (dictname == nil)
  190.                         dictname = argv[index];
  191.                     else
  192.                         {
  193.                         fprintf(stderr, "Error - multiple dictionary "
  194.                                         "files %s and %s!\n",
  195.                                         dictname, argv[index]);
  196.                         errors = true;
  197.                         }
  198.                     break;
  199.                 
  200.                 default:
  201.                     fprintf(stderr, "Error - Unknown option %s\n",
  202.                                     argv[index]);
  203.                     errors = true;
  204.                     break;
  205.                 
  206.                 }
  207.             
  208.             }
  209.         else if (language == nocode)
  210.             {
  211.     
  212. //    argv[index] is the name of an input file; if
  213. //        "language" has not changed since initialization,
  214. //        set "language" according to file name
  215.             
  216.             thetail = argv[index] + strlen(argv[index]) - 2;
  217.             if (strcmp(thetail, ".p") == 0)
  218.                 language = pascalcode;
  219.             else if (strcmp(thetail, ".c") == 0)
  220.                 language = ccode;
  221.             
  222.             }
  223.         
  224.         }
  225.     
  226. //    exit if errors were found in the first pass
  227.     
  228.     if (errors)
  229.         exit(2);
  230.     
  231. //    if "language" is still unknown, set it to Pascal
  232.     
  233.     if (language == nocode)
  234.         language = pascalcode;
  235.     
  236. //    load the case table
  237.     
  238.     if (sensitive)
  239.         thehandle = GetResource('TABL', 4002);
  240.     else
  241.         thehandle = GetResource('TABL', 4001);
  242.     HLock(thehandle);
  243.     CASETABLE = (unsigned char *)*thehandle;
  244.     
  245. //    copy the dictionary into the symbol table
  246.     
  247.     if (dictname == nil)
  248.         {
  249.         fprintf(stdout, "Error - no dictionary file specified!\n");
  250.         exit(2);
  251.         }
  252.     
  253.     symbols = parser(dictname, language);
  254.     if (symbols == nil)
  255.         exit(2);
  256.     
  257. //    if "outputname" has been found, open the output file
  258.     
  259.     if (outputname != nil)
  260.         {
  261.         output = openoutput(argv[++index], output);
  262.         if (output < 0)
  263.             {
  264.             fprintf(stderr, "Error - Unable to open "
  265.                             "output file %s!\n", argv[index]);
  266.             exit(2);
  267.             }
  268.         }
  269.     
  270. //    "input" is the fd of the input file, initially stdin
  271. //    "thehandle" is the input buffer, initially empty
  272. //    "buffersize" is the size of "thehandle"
  273.     
  274.     input = stdinfd;
  275.     thehandle = NewHandle(0);
  276.     buffersize = 0;
  277.     
  278. //    command line interpreter: second pass
  279.     
  280.     for (index = 1; index < argc; index++)
  281.         {
  282.     
  283. //    skip all options (read in first pass)
  284.         
  285.         if (argv[index][0] == '-')
  286.             {
  287.             switch (argv[index][1])
  288.                 {
  289.                 case 'D':
  290.                 case 'O':
  291.                 case 'd':
  292.                 case 'o':
  293.                     index++;
  294.                 }
  295.             }
  296.         else
  297.             {
  298.     
  299. //    argv[index] is the name of an input file; open
  300. //        the file and read it into the input buffer
  301.             
  302.             input = open(argv[index], O_RDONLY);
  303.             if (input < 0)
  304.                 {
  305.                 fprintf(stderr, "Error - Unable to open "
  306.                                 "input file %s!\n", argv[index]);
  307.                 exit(2);
  308.                 }
  309.             
  310.             buffersize = readinput(input, thehandle);
  311.             if (buffersize < 0)
  312.                 {
  313.                 fprintf(stderr, "Error - Reading from %s!\n", argv[index]);
  314.                 exit(2);
  315.                 }
  316.             
  317.             close(input);
  318.             
  319. //    call "filter" to read the input buffer and write
  320. //        filtered output
  321.             
  322.             HLock(thehandle);
  323.             filter(*thehandle, buffersize, output, language, symbols);
  324.             HUnlock(thehandle);
  325.             
  326.             }
  327.         
  328.         }
  329.     
  330. //    if "input" is still a standard unit number, then no
  331. //        input file was opened, and input must be from
  332. //        standard input
  333.     
  334.     if (stdunit(input))
  335.         {
  336.         
  337.         buffersize = readinput(input, thehandle);
  338.         if (buffersize < 0)
  339.             {
  340.             fprintf(stderr, "Error - Reading from standard input!\n");
  341.             exit(2);
  342.             }
  343.         
  344. //    call "filter" to read the input buffer and write
  345. //        filtered output
  346.         
  347.         HLock(thehandle);
  348.         filter(*thehandle, buffersize, output, language, symbols);
  349.         HUnlock(thehandle);
  350.         
  351.         }
  352.     
  353. //    wrapup:  dispose of the input buffer, close "output"
  354. //        if the program opened it and dispose of the symbol table
  355.     
  356.     DisposHandle(thehandle);
  357.     
  358.     if (notstdunit(output))
  359.         close(output);
  360.     destroy();
  361.     
  362.     exit(0);
  363.     
  364.     }
  365.     
  366. //////////////////////////////////////////////////////////////////
  367. //
  368. //        initmac
  369. //        -------
  370. //        initialize any necessary managers and whatnot.
  371. //
  372. //////////////////////////////////////////////////////////////////
  373.     
  374. void initmac()
  375.     {
  376.     
  377.     InitGraf((Ptr)&qd.thePort);
  378.     SetFScaleDisable(true);
  379.     
  380.     InitCursorCtl(nil);
  381.     
  382.     }
  383.     
  384. //////////////////////////////////////////////////////////////////
  385. //
  386. //        openoutput
  387. //        ----------
  388. //        open the output file.  returns the fd or, if an error
  389. //        occurs, the error flag.
  390. //
  391. //////////////////////////////////////////////////////////////////
  392.     
  393. int openoutput(char *thename, int output)
  394.     {
  395.     
  396.     FInfo                theinfo;
  397.     
  398. //    if "output" is not a standard unit, then an output
  399. //        file must have already be open
  400.     
  401.     if (notstdunit(output))
  402.         {
  403.         fprintf(stderr, "Warning - additional output "
  404.                         "file %s ignored!\n", thename);
  405.         return(output);
  406.         }
  407.  
  408. //    open the output file for writing (O_WRONLY),
  409. //        creating it if necessary (O_CREAT) and
  410. //        zeroing it otherwise (O_TRUNC)
  411.     
  412.     output = open(thename, O_WRONLY + O_CREAT + O_TRUNC);
  413.     if (output < 0)
  414.         return(output);
  415.  
  416. //    if the file was created by "open", it will be
  417. //        untyped, so set the type to TEXT and MPS
  418.     
  419.     if (getfinfo(thename, 0, &theinfo))
  420.         {
  421.         fprintf(stderr, "Warning - unable to get info for "
  422.                         "output file %s!\n", thename);
  423.         return(output);
  424.         }
  425.     
  426.     theinfo.fdType = 'TEXT';
  427.     theinfo.fdCreator = 'MPS ';
  428.     
  429.     if (setfinfo(thename, 0, &theinfo))
  430.         fprintf(stderr, "Warning - unable to set info for "
  431.                         "output file %s!\n", thename);
  432.     
  433.     return(output);
  434.     
  435.     }
  436.     
  437. //////////////////////////////////////////////////////////////////
  438. //
  439. //        readinput
  440. //        ---------
  441. //        this routine reads an input file into the input buffer and
  442. //        returns the new size of the buffer or, if a read error
  443. //        occurs, the error flag.
  444. //
  445. //////////////////////////////////////////////////////////////////
  446.     
  447. int readinput(int input, Handle thehandle)
  448.     {
  449.     
  450.     int                buffersize;
  451.     int                readsize;
  452.     
  453.     buffersize = 0;
  454.     
  455.     SetHandleSize(thehandle, 1024);
  456.     HLock(thehandle);
  457.     
  458.     while ((readsize = read(input, *thehandle + buffersize, 1024)) > 0)
  459.         {
  460.         buffersize += readsize;
  461.         HUnlock(thehandle);
  462.         SetHandleSize(thehandle, buffersize + 1024);
  463.         HLock(thehandle);
  464.         }
  465.     
  466.     if (readsize < 0)
  467.         return(readsize);
  468.     
  469.     HUnlock(thehandle);
  470.     SetHandleSize(thehandle, buffersize + 1024);
  471.     
  472.     return(buffersize);
  473.     
  474.     }
  475.     
  476. //////////////////////////////////////////////////////////////////
  477. //
  478. //        filter
  479. //        ------
  480. //        this routine does the main work of the program.
  481. //
  482. //////////////////////////////////////////////////////////////////
  483.     
  484. int filter(char *inbuffer, int buffersize, int output,
  485.                 codetype language, node *symbols)
  486.     {
  487.     
  488.     int                inposition;
  489.     int                outposition;
  490.     int                thetoken;
  491.     node                *thenode;
  492.     int                thelength;
  493.     Handle            thehandle;
  494.     char                *classtable;
  495.     char                *statetable;
  496.     char                outbuffer[truebuffsize];
  497.     int                thestate;
  498.     unsigned char    thechar;
  499.     int                theclass;
  500.     int                newstate;
  501.     int                writesize;
  502.  
  503. //    “inposition” is the current read position
  504. //    “outposition” is the current write position
  505. //    “thetoken” is the position of the beginning of the
  506. //        current identifier
  507.     
  508.     inposition = 0;
  509.     outposition = 0;
  510.     thetoken = 0;
  511.  
  512. //    “classtable” converts characters into classes
  513.     
  514.     thehandle = GetResource('TABL', 1001);
  515.     HLock(thehandle);
  516.     classtable = *thehandle;
  517.  
  518. //    “statetable” is the state machine
  519.     
  520.     if (language == pascalcode)
  521.         thehandle = GetResource('TABL', 3001);
  522.     else
  523.         thehandle = GetResource('TABL', 3002);
  524.     HLock(thehandle);
  525.     statetable = *thehandle;
  526.     
  527. //    start the machine in state 0
  528.     
  529.     thestate = 0;
  530.     while (inposition < buffersize)
  531.         {
  532.  
  533. //    read the next character, find its class
  534. //        and the new state
  535.         
  536.         thechar = inbuffer[inposition++];
  537.         theclass = classtable[thechar];
  538.         newstate = statetable[classcount * thestate + theclass];
  539.         
  540.         switch (newstate)
  541.             {
  542.  
  543. //    found an identifier:  if it is in the symbol table,
  544. //        replace it with the table's data.  Then go to
  545. //        state 0.
  546.             
  547.             case -1:
  548.                 inposition--;
  549.                 outbuffer[outposition] = '\0';
  550.                 thenode = lookup(symbols, &outbuffer[thetoken]);
  551.                 if (thenode != nil)
  552.                     {
  553.                     outposition -= strlen(&outbuffer[thetoken]);
  554.                     thelength = strlen(thenode->data);
  555.                     BlockMove((Ptr)thenode->data,
  556.                                     &outbuffer[outposition], thelength);
  557.                     outposition += thelength;
  558.                     }
  559.                 newstate = 0;
  560.                 break;
  561.  
  562. //    retract if going from state 2 to state 0; otherwise,
  563. //        copy input to output
  564.             
  565.             case 0:
  566.                 if (thestate == 2)
  567.                     inposition--;
  568.                 else
  569.                     outbuffer[outposition++] = thechar;
  570.                 break;
  571.  
  572. //    reading an identifier:  if this is the beginning,
  573. //        record the position for later use.  Then, fall
  574. //        through to the default
  575.             
  576.             case idstate:
  577.                 if (thestate != idstate)
  578.                     thetoken = outposition;
  579.  
  580. //    all other cases, copy input to output
  581.             
  582.             default:
  583.                 outbuffer[outposition++] = thechar;
  584.                 break;
  585.             
  586.             }
  587.  
  588. //    if the output buffer fills up, and we're not in the
  589. //        middle of an identifier, write it to disk
  590.         
  591.         if ((outposition >= nombuffsize)
  592.                         && (thestate != idstate) && (newstate != idstate))
  593.             {
  594.             outposition = writeoutput(output, outbuffer, outposition);
  595.             if (outposition < 0)
  596.                 return(outposition);
  597.             }
  598.         
  599.         thestate = newstate;
  600.         
  601.         }
  602.  
  603. //    write the output buffer to disk
  604.     
  605.     writesize = write(output, outbuffer, outposition);
  606.     return(writesize);
  607.     
  608.     }
  609.     
  610. //////////////////////////////////////////////////////////////////
  611. //
  612. //        writeoutput
  613. //        ----------
  614. //        this routine flushes the output buffer by writing
  615. //        it to the output file.  It returns the new size of the
  616. //        buffer or, if a write error occurs, the error flag.
  617. //
  618. //////////////////////////////////////////////////////////////////
  619.     
  620. int writeoutput(int output, char *outbuffer, int buffersize)
  621.     {
  622.     
  623.     int                writesize;
  624.     
  625.     writesize = write(output, outbuffer, nombuffsize);
  626.     
  627.     if (writesize < 0)
  628.         return(writesize);
  629.     
  630.     buffersize -= writesize;
  631.     BlockMove(outbuffer + writesize, outbuffer, buffersize);
  632.     
  633.     return(buffersize);
  634.     
  635.     }
  636.     
  637. //////////////////////////////////////////////////////////////////
  638. //
  639. //        parser
  640. //        ------
  641. //        this routine creates the symbol table and stores the
  642. //        Canon dictionary in it.
  643. //
  644. //////////////////////////////////////////////////////////////////
  645.     
  646. node *parser(char *dictname, codetype language)
  647.     {
  648.     
  649.     Handle            thehandle;
  650.     char                *parsetable;
  651.     char                *classtable;
  652.     char                *statetable;
  653.     int                thefile;
  654.     int                buffersize;
  655.     char                *buffer;
  656.     node                *symbols;
  657.     int                thestate;
  658.     int                newstate;
  659.     int                theline;
  660.     int                errors;
  661.     int                thetoken;
  662.     char                *thekey;
  663.     char                *thedata;
  664.     char                *dummy;
  665.     char                **thestring;
  666.     
  667.     thedata = nil;
  668.     
  669. //    "parsetable" is the parser's state machine
  670.     
  671.     thehandle = GetResource('TABL', 1000);
  672.     HLock(thehandle);
  673.     parsetable = *thehandle;
  674.     
  675. //    "classtable" is the character class table
  676.     
  677.     thehandle = GetResource('TABL', 1001);
  678.     HLock(thehandle);
  679.     classtable = *thehandle;
  680.     
  681. //    "statetable" is the lexical state machine
  682.     
  683.     if (language == pascalcode)
  684.         thehandle = GetResource('TABL', 2001);
  685.     else
  686.         thehandle = GetResource('TABL', 2002);
  687.     HLock(thehandle);
  688.     statetable = *thehandle;
  689.     
  690. //    open the dictionary file...
  691.     
  692.     thefile = open(dictname, O_RDONLY);
  693.     if (thefile < 0)
  694.         {
  695.         fprintf(stderr, "Error - Unable to open "
  696.                         "dictionary file %s!\n", dictname);
  697.         return(nil);
  698.         }
  699.     
  700. //    and read it into the buffer
  701.     
  702.     DICTIONARY = NewHandle(0);
  703.     buffersize = readinput(thefile, DICTIONARY);
  704.     if (buffersize < 0)
  705.         {
  706.         fprintf(stderr, "Error - Unable to read %s!\n", dictname);
  707.         close(thefile);
  708.         return(nil);
  709.         }
  710.     
  711.     close(thefile);
  712.     
  713.     HLock(DICTIONARY);
  714.     buffer = (char *)*DICTIONARY;
  715.     
  716. //    "symbols" is the symbol table
  717.     
  718.     symbols = createnode(NOTHING, NOTHING);
  719.     
  720. //    start the machine in state 0, and on line 1
  721.     
  722.     thestate = 0;
  723.     theline = 1;
  724.     errors = 0;
  725.     
  726. //    read the first identifier into “thekey”
  727.     
  728.     thekey = gettoken(buffer, buffersize,
  729.                     classtable, statetable, &thetoken);
  730.     
  731.     while (thetoken >= 0)
  732.         {
  733.         
  734.         newstate = parsetable[3 * thestate + thetoken];
  735.         
  736.         switch (newstate)
  737.             {
  738.     
  739. //    if we got here from state 1, then we read only one
  740. //        identifier; if from state 2, we read both “thekey”
  741. //        and “thedata”
  742. //    state 0 is the beginning of a line, so increment the
  743. //        line counter and set “thestring” to “thekey”
  744.             
  745.             case 0:
  746.                 if (thestate == 1)
  747.                     thetoken = insert(symbols, thekey, thekey, 0);
  748.                 else if (thestate == 2)
  749.                     thetoken = insert(symbols, thekey, thedata, 0);
  750.                 if (thetoken == 4)
  751.                     {
  752.                     fprintf(stderr, "\n#\tDuplicate key in dictionary "
  753.                                     "file\n\tFile \"%s\"; Line %d\n",
  754.                                     dictname, theline);
  755.                     errors++;
  756.                     }
  757.                 theline++;
  758.                 thestring = &thekey;
  759.                 break;
  760.     
  761. //    having read one identifier into “thekey”, the
  762. //        next one should go into “thedata”
  763.             
  764.             case 1:
  765.                 thestring = &thedata;
  766.                 break;
  767.     
  768. //    having read one identifier into “thekey”, and the
  769. //        next one “thedata”, read anything else into
  770. //        “dummy”
  771.             
  772.             case 2:
  773.                 thestring = &dummy;
  774.                 break;
  775.     
  776. //    case 3 is the error case; if we just got here, write
  777. //        an error message
  778.             
  779.             case 3:
  780.                 if (thestate != newstate)
  781.                     fprintf(stderr, "\n#\tError in dictionary file\n"
  782.                                     "\tFile \"%s\"; Line %d\n", dictname,
  783.                                     theline);
  784.                 errors++;
  785.                 break;
  786.             
  787.             }
  788.         
  789.         thestate = newstate;
  790.         *thestring = gettoken(buffer, buffersize,
  791.                         classtable, statetable, &thetoken);
  792.         
  793.         }
  794.     
  795.     if (errors > 0)
  796.         {
  797.         destroy();
  798.         fprintf(stderr, "\n%d errors found in dictionary\n", errors);
  799.         return(nil);
  800.         }
  801.     
  802. //    dump(symbols);
  803.     return(symbols);
  804.     
  805.     }
  806.     
  807. //////////////////////////////////////////////////////////////////
  808. //
  809. //        gettoken
  810. //        --------
  811. //        This routine reads the dictionary file until it finds a
  812. //        token (which it returns) or the end of the file (in
  813. //        which case it returns -1).
  814. //
  815. //////////////////////////////////////////////////////////////////
  816.     
  817. char *gettoken(char *buffer, int buffersize,
  818.                 char *classtable, char *statetable, int *thetoken)
  819.     {
  820.     
  821.     static int        position = 0;
  822.     
  823.     int                thestate;
  824.     unsigned char    thechar;
  825.     int                theclass;
  826.     int                newstate;
  827.     int                thestart;
  828.     
  829.     thestart = 0;
  830.     
  831. //    start the machine in state 0
  832.     
  833.     thestate = 0;
  834.     
  835.     while (position < buffersize)
  836.         {
  837.     
  838. //    read the next character, look up its class,
  839. //        and get the new state
  840.         
  841.         thechar = buffer[position++];
  842.         theclass = classtable[thechar];
  843.         newstate = statetable[classcount * thestate + theclass];
  844.         
  845.         switch (newstate)
  846.             {
  847.     
  848. //    -3 => ERR, -2 => CR; in either case, just return the
  849. //        the token number
  850.             
  851.             case -3:
  852.             case -2:
  853.                 buffer[position - 1] = '\0';
  854.                 *thetoken = - 1 - newstate;
  855.                 return(nil);
  856.     
  857. //    -1 => ID; return the token number
  858. //        and the identifier in “thestring”
  859.             
  860.             case -1:
  861.                 position--;
  862.                 *thetoken = - 1 - newstate;
  863.                 return(&buffer[thestart]);
  864.             
  865.             case 0:
  866.                 if (thestate == 1)
  867.                     position--;
  868.                 break;
  869.             
  870.             case 1:
  871.                 break;
  872.             
  873.             case 2:
  874.                 break;
  875.             
  876.             }
  877.         
  878.         if (newstate != 2)
  879.             buffer[position - 1] = '\0';
  880.         else if (thestate == 0)
  881.             thestart = position - 1;
  882.         
  883.         thestate = newstate;
  884.         
  885.         }
  886.     
  887.     *thetoken = -10;
  888.     return(nil);
  889.     
  890.     }
  891.     
  892. //////////////////////////////////////////////////////////////////
  893. //
  894. //        createnode
  895. //        ----------
  896. //        create and initialize a new node
  897. //
  898. //////////////////////////////////////////////////////////////////
  899.     
  900. node *createnode(char *thekey, char *thedata)
  901.     {
  902.     
  903.     block                *theblock;
  904.     node                *thenode;
  905.     
  906.     if (MEMORY && (MEMORY->free < blocksize))
  907.         thenode = &(MEMORY->data[MEMORY->free++]);
  908.     else
  909.         {
  910.         
  911.         theblock = (block *)NewPtr(sizeof(block));
  912.         if (theblock == nil)
  913.             return(nil);
  914.         
  915.         theblock->previous = MEMORY;
  916.         MEMORY = theblock;
  917.         
  918.         theblock->free = 1;
  919.         thenode = &(MEMORY->data[0]);
  920.         
  921.         }
  922.     
  923.     thenode->key = thekey;
  924.     thenode->balance = 0;
  925.     thenode->left = nil;
  926.     thenode->right = nil;
  927.     thenode->data = thedata;
  928.     
  929.     return(thenode);
  930.     
  931.     }
  932.     
  933. //////////////////////////////////////////////////////////////////
  934. //
  935. //        insert
  936. //        ------
  937. //        Insert a new key into the table and correct balance
  938. //        factors recursively.  The routine returns a queue of
  939. //        path directions.
  940. //
  941. //////////////////////////////////////////////////////////////////
  942.     
  943. unsigned int insert(node *parent, char *thekey, char *thedata, int depth)
  944.     {
  945.     
  946.     int                difference;
  947.     node                *high;
  948.     unsigned int    result;
  949.     node                *low;
  950.     node                *child;
  951.     
  952. //    if thekey matches this node, then return an error
  953. //        (duplicate keys)
  954.     
  955.     difference = compare(thekey, parent->key);
  956.     if (difference == 0)
  957.         return(4);
  958.     
  959. //    if there's a slot for the new node, then create it and return
  960. //        1 if it is to the left of parent and 2 if to the right
  961. //    else determine high, the next step in the search path
  962.     
  963.     if (difference < 0)
  964.         {
  965.         high = parent->left;
  966.         if (high == nil)
  967.             {
  968.             parent->left = createnode(thekey, thedata);
  969.             return(1);
  970.             }
  971.         }
  972.     else
  973.         {
  974.         high = parent->right;
  975.         if (high == nil)
  976.             {
  977.             parent->right = createnode(thekey, thedata);
  978.             return(2);
  979.             }
  980.         }
  981.     
  982. //    now continue the search by calling “insert” recursively
  983. //    if the result is 0 (no balancing needed at this level) or
  984. //        the result is 4 (duplicate key), return
  985.     
  986.     result = insert(high, thekey, thedata, depth + 1);
  987.     if ((result == 0) || (result == 4))
  988.         return(result);
  989.     
  990. //    the low 4 bits of “result” indicate the direction of the
  991. //        search path leaving “high”; increment high's balance
  992. //        if the path goes left, and decrement it if the path
  993. //        goes right
  994.     
  995.     if (result % 16 == 1)
  996.         high->balance++;
  997.     else
  998.         high->balance--;
  999.     
  1000. //    if the balance is now zero, no further correction of balances
  1001. //        is needed, so return
  1002. //    if it's ±1, push the direction away from “parent” onto the
  1003. //        “result” stack and return it
  1004. //    if it's ±2, continue to balancing transformation
  1005.     
  1006.     switch (high->balance)
  1007.         {
  1008.         case 0:
  1009.             return(0);
  1010.         case 1:
  1011.         case -1:
  1012.             return((result << 4) + ((difference < 0) ? 1 : 2));
  1013.         case 2:
  1014.         case -2:
  1015.             break;
  1016.         }
  1017.     
  1018. //    use the direction away from “high” to find “low”, then
  1019. //        switch on that direction and the next one
  1020. //    the easiest way to follow these transformations is to
  1021. //        refer to the pictures
  1022.     
  1023.     low = (result % 16 == 1) ? high->left : high->right;
  1024.     switch (result % 256)
  1025.         {
  1026.         
  1027.         case 0x11:    //    left-left case
  1028.             
  1029.             high->left = low->right;
  1030.             low->right = high;
  1031.             if (difference < 0)
  1032.                 parent->left = low;
  1033.             else
  1034.                 parent->right = low;
  1035.             high->balance = 0;
  1036.             low->balance = 0;
  1037.             return(0);
  1038.         
  1039.         case 0x12:    //    right-left case
  1040.             
  1041.             child = low->left;
  1042.             high->right = child->left;
  1043.             low->left = child->right;
  1044.             if (difference < 0)
  1045.                 parent->left = child;
  1046.             else
  1047.                 parent->right = child;
  1048.             child->left = high;
  1049.             child->right = low;
  1050.             child->balance = 0;
  1051.             low->balance = 0;
  1052.             high->balance = 0;
  1053.             result &= 0xF00;
  1054.             if (result == 0x100)
  1055.                 low->balance = -1;
  1056.             else if (result == 0x200)
  1057.                 high->balance = 1;
  1058.             return(0);
  1059.         
  1060.         case 0x21:    //    left-right case
  1061.             
  1062.             child = low->right;
  1063.             low->right = child->left;
  1064.             high->left = child->right;
  1065.             if (difference < 0)
  1066.                 parent->left = child;
  1067.             else
  1068.                 parent->right = child;
  1069.             child->left = low;
  1070.             child->right = high;
  1071.             child->balance = 0;
  1072.             low->balance = 0;
  1073.             high->balance = 0;
  1074.             result &= 0xF00;
  1075.             if (result == 0x100)
  1076.                 high->balance = -1;
  1077.             else if (result == 0x200)
  1078.                 low->balance = 1;
  1079.             return(0);
  1080.         
  1081.         case 0x22:    //    right-right case
  1082.             
  1083.             high->right = low->left;
  1084.             low->left = high;
  1085.             if (difference < 0)
  1086.                 parent->left = low;
  1087.             else
  1088.                 parent->right = low;
  1089.             high->balance = 0;
  1090.             low->balance = 0;
  1091.             return(0);
  1092.         
  1093.         }
  1094.     
  1095.     }
  1096.     
  1097. //////////////////////////////////////////////////////////////////
  1098. //
  1099. //        lookup
  1100. //        ------
  1101. //        Find a key in the table
  1102. //
  1103. //////////////////////////////////////////////////////////////////
  1104.     
  1105. node *lookup(node *thetable, char *thekey)
  1106.     {
  1107.     
  1108.     node                *thenode;
  1109.     int                difference;
  1110.     
  1111.     thenode = thetable;
  1112.     
  1113.     while (difference = compare(thekey, thenode->key))
  1114.         {
  1115.         if (difference < 0)
  1116.             thenode = thenode->left;
  1117.         else
  1118.             thenode = thenode->right;
  1119.         if (thenode == nil)
  1120.             return(nil);
  1121.         }
  1122.     
  1123.     return(thenode);
  1124.     
  1125.     }
  1126.     
  1127. //////////////////////////////////////////////////////////////////
  1128. //
  1129. //        destroy
  1130. //        -------
  1131. //        Dispose of the table
  1132. //
  1133. //////////////////////////////////////////////////////////////////
  1134.     
  1135. void destroy()
  1136.     {
  1137.     
  1138.     block                *theblock;
  1139.     block                *newblock;
  1140.     
  1141.     DisposHandle(DICTIONARY);
  1142.     
  1143.     theblock = MEMORY;
  1144.     while (theblock)
  1145.         {
  1146.         newblock = theblock->previous;
  1147.         DisposPtr((Ptr)theblock);
  1148.         theblock = newblock;
  1149.         }
  1150.     
  1151.     }
  1152.     
  1153. //////////////////////////////////////////////////////////////////
  1154. //
  1155. //        dump
  1156. //        ----
  1157. //        Dump the table
  1158. //
  1159. //////////////////////////////////////////////////////////////////
  1160.     
  1161. void dump(node *thenode)
  1162.     {
  1163.     
  1164.     if (thenode == nil)
  1165.         return;
  1166.     
  1167.     dump(thenode->left);
  1168.     printf("key %s; data %s; left %s; right %s\n",
  1169.                     thenode->key, thenode->data,
  1170.                     thenode->left ? thenode->left->key : "nil",
  1171.                     thenode->right ? thenode->right->key : "nil");
  1172.     dump(thenode->right);
  1173.     
  1174.     }
  1175.     
  1176. //////////////////////////////////////////////////////////////////
  1177. //
  1178. //        compare
  1179. //        -------
  1180. //        replacement for “strcmp” routine; case sensitivity is
  1181. //        determined by the global transliteration table CASETABLE.
  1182. //
  1183. //////////////////////////////////////////////////////////////////
  1184.     
  1185. int compare(unsigned char *string1, unsigned char *string2)
  1186.     {
  1187.     
  1188.     register int    char1;
  1189.     register int    char2;
  1190.     register int    difference;
  1191.     
  1192.     char1 = *string1++;
  1193.     char2 = *string2++;
  1194.     
  1195.     while (char1 || char2)
  1196.         
  1197.         {
  1198.         
  1199.         difference = CASETABLE[char1] - CASETABLE[char2];
  1200.         if (difference)
  1201.             return(difference);
  1202.         
  1203.         char1 = *string1++;
  1204.         char2 = *string2++;
  1205.         
  1206.         }
  1207.     
  1208.     return(0);
  1209.     
  1210.     }
  1211.     
  1212. //////////////////////////////////////////////////////////////////
  1213.